#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: title023.py 
@version:
@time: 2023/05/14

 NC28.最小覆盖子串

给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

输入
"XDOYEZODEYXNZ","XYZ"
输出
"YXNZ"


step 1：建立哈希表，遍历字符串T，统计各个字符出现的频率，频率计为负数。
step 2：依次遍历字符串S，如果匹配则将哈希表中的相应的字符加1。
step 3：在遍历过程中维护一个窗口，如果哈希表中所有元素都大于0，
意味着已经找全了，则窗口收缩向左移动，找最小的窗口，
如果不满足这个条件则窗口右移继续匹配。
窗口移动的时候需要更新最小窗口，以取得最短子串。
step 4：如果匹配到最后，窗口left（初始为-1）也没有右移，说明没有找到，返回空串即可。
step 5：最后使用字符串截取函数，截取刚刚记录下的窗口即可得到符合条件的最短子串。
"""


class Solution:
    # 检查是否有小于0的
    def check(self, hash: dict()):
        for key, value in hash.items():
            if value < 0:
                return False
        return True

    def minWindow(self, S: str, T: str) -> str:
        cnt = len(S) + 1
        # 记录目标字符串T的字符个数
        hash = dict()
        for i in range(len(T)):
            if T[i] in hash:
                # 初始化哈希表都为负数，找的时候再加为正
                hash[T[i]] -= 1
            else:
                hash[T[i]] = -1
        slow = 0
        fast = 0
        left = -1
        # 记录左右区间
        right = -1
        while fast < len(S):
            c = S[fast]
            # 目标字符匹配+1
            if c in hash:
                hash[c] += 1
            # 没有小于0的说明都覆盖了，缩小窗口
            while Solution.check(self, hash):
                # 取最优解
                if cnt > fast - slow + 1:
                    cnt = fast - slow + 1
                    left = slow
                    right = fast
                c = S[slow]
                if c in hash:
                    # 缩小窗口的时候减1
                    hash[c] -= 1
                # 窗口缩小
                slow += 1
            fast += 1
        # 找不到的情况
        if left == -1:
            return ""
        return S[left: right + 1]


assert Solution().minWindow("XDOYEZODEYXNZ", "XYZ") == "YXNZ"
print("测试成功")
